package algorithm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class leetcode_0018 {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> total=new ArrayList<>();
        if(nums.length<=3) ;
        else {
            Arrays.sort(nums);
            int len=nums.length;
            for(int i=0;i<len-3;){
                for(int j=i+1;j<len-2;){
                    int l=len-1;
                    for(int k=j+1;k<len-1&&k<l;){

                        if(nums[i]+nums[k]+nums[j]==target-nums[l]){
                            List<Integer> list=new ArrayList<>();
                            list.add(nums[i]);list.add(nums[j]);
                            list.add(nums[k]);list.add(nums[l]);
                            total.add(list);
                            l--;
                            while(k<l&&nums[l]==nums[l+1]) l--;
                        }
                        else if(nums[i]+nums[k]+nums[j]<target-nums[l]){
                            l=len-1;++k;while(k<l&&nums[k-1]==nums[k]) ++k;
                            continue;
                        }
                        else{
                            l--;while(k<l&&nums[l]==nums[l+1]) l--;
                        }

                    }
                    ++j;while(j<len-2&&nums[j-1]==nums[j]) ++j;
                }
                ++i;while(i<len-3&&nums[i-1]==nums[i])++i;
            }
        }
        return total;
    }
}
